/**
 * 给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。
 */

const isValid = (str) => {
  if (!(str.length % 2)) return false
  let stk = [] //栈
  let map = new Map([')', '('], ['}', '{'], [']', '['])
  str.split('').forEach((element) => {
    if (map.has(element)) {
      // 栈长度为0，栈的最后一项不是‘所要匹配的有括号’
      if (!stk.length || map.get(element) !== stk[stk.length - 1]) {
        return false
      }
      stk.pop()
    } else {
      // 左括号-入栈
      stk.push(element)
    }
  })
  return !stk.length
}

/**
 * stack实现queue
 * queue实现stack
 */

class myQueue {
  constructor() {
    this.pushArr = []
    this.popArr = []
  }

  //将第一个元素放入队列的尾部
  push(value) {
    this.pushArr.push(value)
  }

  //从队列首部移除元素
  pop() {
    if (!this.popArr.length) {
      while (this.pushArr.length) {
        this.popArr.push(this.pushArr.pop())
      }
      return this.popArr.pop()
    }
  }

  /**返回队列首部的元素 */
  peek() {
    if (!this.popArr.length) {
      while (this.pushArr.length) {
        this.popArr.push(this.pushArr.pop())
      }
    }
    return this.popArr[this.popArr.length - 1]
  }

  /**返回队列是否为空 */
  empty() {
    return !this.pushArr.length && !this.popArr.length
  }
}

/**
 * 数据流中的第 K 大元素
 * 优先队列实现
 */
class KthLargest {
  //k表示第k个最大元素
  //arr表示初始化的数据数组
  constructor(k, arr) {
    this.k = k
    this.minHeap = [null]
    for (let i = 0; i < arr.length; i++) {
      this.add(arr[i])
    }
  }

  add = (val) => {
    if (this.minHeap.length <= this.k) {
      // 最小堆没满，放到最小堆
      this.minHeap.push(val)
      // 上浮最新的元素，维护堆的秩序
      this.up(this.minHeap.length - 1)
    }
  }

  /**
   * 最小堆的上浮操作
   * @param {number} idx 要上浮的元素下标
   */

  up = (idx) => {
    let parent = Math.floor(id / 2)
    if (parent > 1 && this.minHeap[parent] > this.minHeap[idx]) {
      swap(this.minHeap, arent, idx)
      this.up(parent)
    } else {
      if (val > this.minHeap[1]) {
        // 新的元素比最小堆堆顶大，替换最小堆堆顶
        this.minHeap[1] = val
        // 下沉这个元素，维护堆的秩序
        this.down(1)
      }
      // 否则直接丢弃这个元素
      return this.minHeap[1]
    }
  }

  down = (idx) => {
    let to = idx
    // 和左子元素比较
    let left = idx * 2
    if (left < this.minHeap.length && this.minHeap[left] < this.minHeap[to]) {
      to = left
    }
    // 和右子元素比较
    let right = idx * 2 + 1
    if (right < this.minHeap.length && this.minHeap[right] < this.minHeap[to]) {
      to = right
    }
    if (to !== idx) {
      swap(this.minHeap, to, idx)
      // 递归下沉
      this.down(to)
    }
  }
}

//splice方法
KthLargestFun2 = (key, arr) => {
  this.minHeap = arr.sort((a, b) => b - a)
  this.k = key
}

KthLargestFun2.prototype.add = (num) => {
  let pos = this.minHeap.length
  for (let i = 0; i < pos; i++) {
    if (val >= this.minHeap[i]) {
      pos = i
      break
    }
  }
  this.minHeap.splice(pos, 0, val)
  return this.minHeap[this.key - 1]
}

/**
 * 双端队列返回滚动窗口中的最大值
 */

maxSlidingWindow = (nums, k) => {
  const queue = []
  const result = []
  for (let i = 0; i < nums.length; i++) {
    if (i - queue[0] >= k) {
      queue.shift()
    }
    while (nums[queue[queue.length - 1]] <= nums[i]) {
      queue.pop()
    }
    queue.push(i)
    if (i >= k - 1) {
      result.push(nums[queue[0]])
    }
  }
  return result
}
